package history.study.tow_pointer;

/**
 * 分隔链表
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 算法思想：快指针去搜刮链表后面满足条件的节点，慢指针就指向当前已经满足条件的子链表最后一个节点；
 *           快指针一旦找到满足条件的，就将此节点与慢指针后面的节点进行交换；当快指针遍历结束后此链表就符合条件
 */
public class LeetCode_86 {
    public static void main(String[] args) {
        ListNode listNode1  = new ListNode(1);
        ListNode listNode2  = new ListNode(4);
        ListNode listNode3  = new ListNode(3);
        ListNode listNode4  = new ListNode(2);
        ListNode listNode5  = new ListNode(5);
        ListNode listNode6  = new ListNode(2);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        listNode1 = partition(listNode1, 3);
        while(listNode1.next !=null) {
            System.out.println(listNode1.val);
            listNode1 = listNode1.next;
        }
        System.out.println(listNode1.val);
    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null || x < -200 ||x > 200) return head;
        ListNode slow = head;
        ListNode fast;
        while(slow.next != null && slow.next.val < x)slow =slow.next;
        fast = slow.next;
        while (fast.next != null) {
            if (fast.val < x) {
                ListNode temp1 = slow.next;
                ListNode temp2 = fast.next;
                slow.next = fast;
                fast.next = temp1;
                fast = temp2;
                temp1 = null;
                temp2 = null;
            } else {
                fast = fast.next;
            }
        }
        return head;
    }
}
